package priv.mill.sort;

import java.util.Random;

public class InsertSort {

	// 匿名内部类
	public static class MyArr {

		private int cur;// 当前索引
		private int[] arr;// 数组

		public MyArr() {
			arr = new int[100];
		}

		public void insert(int nextInt) {
			if (cur != 100)
				this.arr[cur++] = nextInt;
		}

		public void printItem() {
			System.out.print("[");
			for (int i = 0; i < cur; i++) {
				System.out.print(arr[i] + ",");
			}
			System.out.println("]");
		}

		public void sort() {
			int in, out;
			for (out = 1; out < cur; out++) {
				int temp = arr[out];// 存储当前的值,空出位置来给交换算法
				in = out;// in的位置可以放东西来，值保存在temp中
				//往前迭代,找出当前值的插入位置
				while (in > 0 && arr[in - 1] >= temp) {
					arr[in] = arr[in - 1];//挪动位置，保持顺序
					--in;//插入位置
				}
				arr[in] = temp;//插入当前值
			}
		}

	}

	public static void main(String[] args) {
		MyArr myArr = new MyArr();
		Random random = new Random(47);
		for (int i = 0; i < 20; i++) {
			myArr.insert(random.nextInt(99));
		}
		myArr.printItem();
		// [74,89,31,65,22,11,1,59,27,13,75,30,30,40,11,37,97,4,80,64,]
		myArr.sort();
		myArr.printItem();
		// [1,4,11,11,13,22,27,30,30,31,37,40,59,64,65,74,75,80,89,97,]
	}
}
